\section{模 $2^{s}$ 分解}

\begin{frame}{模 $2^{s}$ 分解}
  \begin{theorem}%定理1
    当 $s \geqslant 3$ 时， 模 $2^{s}$ 没有原根。实际上， $U_{2^s}=\left(\mathbb{Z} / 2^{s} \mathbb{Z}\right)^{*}$ 是两个循环子群$\pair{-\bar{1}}, \pair{\bar{5}}$的内直积
  (阶分别为 $2$ 和 $2^{s-2}$), 即
\[
  U_{2^{s}}=\langle-\overline{1}\rangle \times\langle\overline{5}\rangle=
  \left\{\left.(-\overline{1})^{\delta} \cdot \overline{5}^{k}~\right|~
    \delta\in\{0,1\}, k\in \{0,1, \cdots, 2^{s-2}-1\} \right\}.
\]
\end{theorem}

\pause
\begin{example*}
  \[
  \begin{aligned}
   \left(\mathbb{Z} / 2^{3} \mathbb{Z}\right)^{*}
   &= \langle\overline{-1}\rangle \times\langle\overline{5}\rangle\\
   &= \{\overline{1} \cdot \overline{1}, \overline{1} \cdot \overline{5}, \overline{-1} \cdot \overline{1}, \overline{-1} \cdot \overline{5}\}
\pause
   =\{\overline{1}, \overline{5}, \overline{7}, \overline{3}\},\\
   \pause
  \left(\mathbb{Z} / 2^{4} \mathbb{Z}\right)^{*}&= \langle\overline{-1}\rangle \times\langle\overline{5}\rangle\\
  \pause
  &= \{\overline{1} \cdot \overline{1}, \overline{1} \cdot \overline{5}, \overline{1} \cdot \overline{5}^{2}, \overline{1} \cdot \overline{5}^{3}, \overline{-1} \cdot \overline{1},
     \overline{-1} \cdot \overline{5}, \overline{-1} \cdot \overline{5}^{2}, \overline{-1} \cdot \overline{5}^{3}\} \\
     &=  \{\overline{1}, \overline{5}, \overline{9}, \overline{13}, \overline{15}, \overline{11}, \overline{7}, \overline{3}\}.
  \end{aligned}
\]
 \end{example*}

 \begin{proof}
   (1) 首先证明： $5\left(\mod 2^{s}\right)$ 的阶为 $2^{s-2}$. 这只需要证明
   \begin{equation*}
     5^{2^{s-3}} \equiv 1+2^{s-1} \quad\left(\mod 2^{s}\right). \tag{1}
 \end{equation*}
 \end{proof}
\end{frame}

\begin{frame}
\begin{proof}[续]
   因为(1) 式说明 $5^{2^{s-3}} \nequiv 1\left(\mod 2^{s}\right)$; 而两边平方则得到 $5^{2^{s-2}} \equiv 1\left(\mod 2^{s}\right)$.
    \pause
     现用数学归纳法证明 (1) 式。 $s=3$ 时显然。 假设对 $s \geqslant 3$ 成立， 两边平方，得
 \[
   5^{2^{s-2}} \equiv\left(1+2^{s-1}\right)^{2}=1+2^{s}+2^{2 s-2} \equiv 1+2^{s} \quad\left(\mod 2^{s+1}\right)
 \]
 （用到上节引理 1(1), 和 $2 s-2 \geqslant s+1$), 即知 $s+1$ 情形时 (1) 式成立。 (1) 式得证。

 \pause
 (2) 再证明： 同余式 $(-1)^{\delta} 5^{k} \equiv(-1)^{\delta^{\prime}} 5^{k^{\prime}}\left(\mod 2^{s}\right)$ 导致
 \[
   \delta \equiv \delta^{\prime} \left(\mod 2\right), \quad k-k^{\prime} \equiv 0 \left(\mod 2^{s-2}\right).
 \]
\pause
 事实上， 由该同余式得 $(-1)^{\delta} \equiv(-1)^{\delta^{\prime}}\left(\mod 4\right)$, 
故 $\delta \equiv \delta^{\prime}\left(\mod 2\right)$ (因为$\operatorname{ord}_4(-1)=2$). 
 于是该同余式化为
 \[
   5^{k} \equiv 5^{k^{\prime}}, \quad 5^{k-k^{\prime}} \equiv 1 \quad\left(\mod 2^{s}\right).
 \]
 \pause
 因 $\operatorname{ord}_{2^{s}}(5) = 2^{s-2}$, 知 $k-k^{\prime} \equiv 0\left(\mod 2^{s-2}\right)$. 
\pause
 因此， 当 $k$ 遍历模 $2^{s-2}$ 的任一剩余系， $\delta$ 遍历模 $2$ 任一剩余系时， $(-1)^{\delta} 5^{k}$ 取遍 $2 \cdot 2^{s-2}$ 个元素， 模 $2^{s}$ 互不同
 余。 
\pause
 而 $2 \cdot 2^{s-2}=\varphi\left(2^{s}\right)=\sharp \left(\mathbb{Z} / 2^{s} \mathbb{Z}\right)^{*}$, 故定理中等式成立。 
\pause
 这也证明了
 $\langle-\overline{1}\rangle \cap\langle\overline{5}\rangle=\{\overline{1}\}$,
 故 $\left(\mathbb{Z} / 2^{s} \mathbb{Z}\right)^{*}=\langle-\overline{1}\rangle \times\langle\overline{5}\rangle$.

 (3) 最后证明：模$2^s$没有原根。由(2)知任意的$g\in U_{2^s}$可写为$g=ab$, 
 其中$a\in \pair{-\bar{1}}, b\in \pair{\bar{5}}$.
 这样
 \[
   g^{2^{s-2}}=(ab)^{2^{s-2}}=a^{2^{s-2}}b^{2^{s-2}} =1.
 \]
 因此$U_{2^{s}}$中没有$\varphi(2^s)=2^{s-1}$阶元素，
 从而模$2^s$没有原根。
 \end{proof}

 \end{frame}
 \begin{frame}

   上述定理使我们彻底清楚了单位群 $U_{m}=(\mathbb{Z} / m \mathbb{Z})^{*}$ 的结构， 即如下定理。
   \pause
 \begin{theorem}%定理2
 设 $m=2^{s} p_{1}^{s_{1}} p_{2}^{s_{2}} \cdots p_{t}^{s_{t}}$ 为素因子分解， 则单位群 $U_{m}=(\mathbb{Z} / m \mathbb{Z})^{*}$ 有如下分解：
 \[
 U_{m} \cong U_{2^{s}} \times U_{p_{1}^{s_{1}}} \times \cdots \times U_{p_{t}^{s_{t}} }
 \]
 其中 $U_{p_{i}^{s}}=\left\langle g_{i}\right\rangle$ 为
 $p_{i}^{s_{i}-1}\left(p_{i}-1\right)$ 阶循环群 ($1 \leqslant i \leqslant t$);
 $U_{2^{s}}=\langle-\overline{1}\rangle \times\langle\overline{5}\rangle$ 
 是阶为 2 和 $2^{s-2}$ 的两循环群的直积 ( $s \geqslant 3$ 时), 或循环群 ( $s=1,2$ 时).
 \end{theorem}

 \pause
 \begin{proof}
  由孙子分解定理 (§2.5 定理 2 及其系) 知道有环的直和分解
\[
  \begin{aligned}
  \mathbb{Z} / m \mathbb{Z} \stackrel{\sigma}{\rightarrow} \mathbb{Z} / 2^{s} \mathbb{Z} \oplus \mathbb{Z} / p_{1}^{s_{1}} \mathbb{Z} \oplus \cdots \oplus \mathbb{Z} / p_{t}^{s_{t}} \mathbb{Z}, \quad
  \bar{x} \mapsto \left(\bar{x}, \bar{x}, \cdots, \bar{x}\right).
\end{aligned}
\]
另外，我们有群同构
\[
  U(R_1\oplus R_2 \oplus \cdots \oplus R_k)\cong U(R_1)\times U(R_2)\times \cdots \times U(R_k).
\]
故得到定理中的直积分解。
\end{proof}

\pause
定理 2 揭示出：单位群 $U_{m}=(\mathbb{Z} / m \mathbb{Z})^{*}$ 是若干循环群的直积。 这是如下 “有限生成的 Abel 群” (即有有限个生成元的 Abel 群)基本定理的特例：任一有限生成的 Abel 群必是有限个循环群的直积。

% \begin{theorem*}[定理 A]
 %  任一有限生成的 Abel 群必是有限个循环群的直积。
 %\end{theorem*}


\end{frame}

 \begin{frame}{模$m$原根存在的所有情形}
   \begin{theorem}%定理3
   模 $m$ 有原根当且仅当
 \[
 m=p^{k}, 2 p^{k}, 2,4
 \]
 (这里 $p$ 为奇素数).
 \end{theorem}
\pause
 \begin{proof}
   设 $m=p_{1}^{e_{1}} \cdots p_{s}^{e_{s}}$ 为素因子分解。 设 $a$ 为与 $m$ 互素 (这当且当$a$与各$p_i^{e_i}$皆互素) 的任一整数，则由 Euler 定理知
  \[
    a^{\varphi(p_{i}^{e_{i}})} \equiv 1 \quad\left(\mod p_{i}^{e_{i}}\right) \quad(1 \leqslant i \leqslant s).
\]
\pause
令 $M=\left[\varphi\left(p_{1}^{e_{1}}\right), \cdots, \varphi\left(p_{s}^{e_{s}}\right)\right]$ 为最小公倍，
则 $M\mid \varphi(m)=\prod_{i=1}^s \varphi(p_i^{e_i})$.
而且我们有 $a^{M} \equiv 1\left(\mod p_{i}^{e_{i}}\right)$, 故 $a^{M} \equiv 1\left(\mod m\right)$.
\pause
如果模 $m$ 有原根， 则对某个$a$ (与$m$互素) 有$\ord_{m} a=\varphi(m)$. 这样$\varphi(m)\mid M$. 因此必须有
\[
  M=\varphi(m)=\varphi\left(p_{1}^{e_{1}}\right) \cdots \varphi\left(p_{s}^{e_{s}}\right),
\]
故 $\varphi\left(p_{1}^{e_{1}}\right), \cdots, \varphi\left(p_{s}^{e_{s}}\right)$ 需两两互素{\verify}。 
\pause
当 $p>2$ 时， $\varphi\left(p^{e}\right)=p^{e-1}(p-1)$ 为偶数， 故 $m$ 不能含两个不同的奇素数因子。
故 $m$ 仅可为 $p^{k}, 2^{m} p^{k}, 2^{k}$ 之 一 ( $p$ 为奇素数). 
若 $m \geqslant 2$, $\varphi\left(2^{m}\right)=2^{m-1}$ 也是偶数， 故 $2^{m} p^{k}$ 无原根。
而 $2^{k}$ 在 $k \geqslant 3$ 时无原根 (定理 1).
\pause
故 $m$ 仅有可能为 $p^{k}, 2 p^{k}, 2,4$. 而我们已经证明这 4 种情形都有原根。
\end{proof}
\end{frame}


\begin{frame}{普适指数}
\color{gray}
 \begin{definition}%定义1
\color{gray}
   有限群 $G$ 的\emph{普适指数} (universal exponent) $e(G)$ 定义为使
 \[
 x^{e}=1 \quad \text { （对任意~} x \in G \text { ) }
 \]
 的最小正整数 $e$.
 \end{definition}

 \pause
 例如， $e(U_3)=2$, $e(U_8)=2$.

 \pause
 \begin{lemma}
\color{gray}
   (1) 设$G$为有限群。若对任意 $x \in G$有$x^{k}=1$, 则 $e(G) \mid k$.
   特别地，$e(G)\mid \sharp G$.

   (2) 设$G$为有限群。那么$e(G)$ 是所有 $x \in G$ 的阶 $\operatorname{ord}(x)$ 的最小公倍数，
 即
 \[
   e(m)=\lcm\{\operatorname{ord}(x)\mid x\in G\}.
 \]

 (3) 令$G_1,\cdots,G_s$为有限群。那么$e(G_1\times \cdots \times G_s)=[e(G_1),\cdots,e(G_s)]$.
 \end{lemma}

 \pause
 \begin{proof}
\color{gray}
   (1) 令$e(G)=e$, $k=qe+r$为带余除式。那么，
   对任意的$x\in G$, $x^r=x^{k-qe}=x^k\cdot (x^e)^{-q}=1$.
   从而由$e$的最小性知$r=0$. 因此$e\mid k$. 我们知$\operatorname{ord}(x)\mid \sharp G$, 故$x^{\sharp G}=1$, 对任意的$x\in G$. 因此$e(G)\mid \sharp G$.
   \end{proof}
 \end{frame}

 \begin{frame}
\color{gray}
   \begin{proof}[续]
\color{gray}
   (2) 令$e=e(G), e'=\lcm\{\operatorname{ord}(x)\mid x\in G\}.$
    $x^{e}=1$表明$\operatorname{ord}(x)\mid e$. 
   这样$e'\mid e$. 
   又对任意$x\in G$, $x^{e'}=1$. 按普适指数的定义有$e=e'$.

   \pause
   (3) 为了记号的方便，我们等同$G_i$为$G_1\times \cdots \times G_s$的子群$\{1\}\times \cdots\times G_i \times \cdots\{1\}$.
   令$e=e(G_1\times \cdots G_s)$, $e'=[e(G_1),\cdots,e(G_s)]$.
   \pause
   对任意的$i$和任意的$g\in G_i$, $g^{e}=1$, 故由(1)知$e(G_i)\mid e$. 进而$e'\mid e$. 
   \pause
   又对任意的$(g_1,\cdots,g_s)\in G_1\times \cdots \times G_s$, 
 \[
   (g_1,\cdots,g_s)^{e'}=(g_1^{e'},\cdots,g_s^{e'})=(1,\cdots,1).
 \]
 按普适指数的定义有$e=e'$. 
  \end{proof}

\pause
对 $G=U_{m}$, 常记 $e\left(U_{m}\right)=e(m)$. 由(1)知 $e(m) \mid \sharp  U_{m}=\varphi(m)$, 这蕴含了 Euler 定理：
对 $x \in U_{m}$有$x^{\varphi(m)}=1$.

 \pause
 由(3)很容易计算出 $e(m)$: 将 $U_{m}$ 分解为循环群的直积 (定理 2), 则 $e(m)$ 是这些循环群的阶的最小公倍， 即
 \[\tag{2}
 e(m)=\left[e\left(2^{s}\right), e\left(p_{1}^{s_{1}}\right), \cdots, e\left(p_{t}^{s_{t}}\right)\right]=\left[e\left(2^{s}\right), \varphi\left(p_{1}^{s_{1}}\right), \cdots, \varphi\left(p_{t}^{s_{t}}\right)\right],
 \]
 其中 $e\left(2^{s}\right)=1,2$, 或 $2^{s-2}$ (分别当 $s=0$ 和 $1, s=2$, 或 $s \geqslant 3$).

 \pause
 可以证明：模$m$原根存在当且仅当$e(m)=\varphi(m)$.%
 \footnote{应用有限Abel群的结构定理容易发现：有限Abel群$G$为循环群当且仅当$e(G)=\sharp G$.
 回想下，若$m,n$为互素的正整数，则$C_m\times C_n\cong C_{mn}$.}
 例如，由于原根的存在， 
 $e(9)=\varphi(9)=6$,  $e(18)=\varphi(18)=6$.
 \pause
 容易发现蕴含($\Rightarrow$); 
 要证明($\Leftarrow$), 一种方法是从公式(2)出发类似于定理3的证明推导出$m$=$2,4,p^s$或$2p^s$, 其中$p$为奇素数。
 \pause


 \end{frame}



\begin{frame}{小结}

  \begin{enumerate}
    \item $s\geqslant 3$时$U_{2^s}$结构如何？并由此解释下为何模$2^s$没有原根。
    \item $U_m$能如何分解为循环群的直积？
    \item 使得模$m$原根存在的$m$是哪些数？
    \item 何为有限群的普适指数？有哪些性质？
  \end{enumerate}
  
\end{frame}
